package java学习.leetcode.editor.cn;
/**
 * @author 刘世锦
 * 2022-09-18 12:55:45	 当前时间
 */
//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母组成 
// 
// Related Topics 字符串 动态规划 
// 👍 5715 👎 0

public class 最长回文子串{
	public static void main(String[] args) {
		Solution solution = new 最长回文子串().new Solution();
		String s = "cbbd";
//		String s = "babad";
		System.out.println(solution.longestPalindrome(s));
		System.out.println(solution.longestPalindrome1(s));

	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String longestPalindrome1(String s) {
    	String res = "";
		for (int i = 0; i < s.length(); i++) {
			String func = func(s, i, i);
			res=res.length()>func.length()?res:func;
			String func1 = func(s, i, i + 1);
			res=res.length()>func1.length()?res:func1;

		}
		return res;
    }
	public String func(String s ,int i,int j){
    	String result = "";
		/**
		 *         i j
		 *     0 1 2 3
		 * s = c b b d
		 *
		 *
		 */
    	while ( i>=0&& j<s.length() ){
    		if (s.charAt(i)!=s.charAt(j)){
				return result;
    		}else{
//    			若相同，则找到回文子串 [i,j]
				result=s.substring(i,j+1);
				i--;
				j++;
			}
		}
//		System.out.println(result);
    	return result;
	}

	/**
	 * 定义： dp[i][j] [i → j] 是否是回文串  从 i 到 j
	 * 初始化： "" 空串到 j 不是回文
	 *
	 *         i j
	 *      "" b a b a d
	 *  ""     0 0 0 0 0
	 *  b    0 1 0 1 0 0
	 *  a    0 0 1 0 1 0
	 *  b    0 0 0 1 0 0
	 *  a    0 0 0 0 1 0
	 *  d    0 0 0 0 0 1
	 *
	 */
	public String longestPalindrome(String s) {
		int start = 0;
		int end = 0;
		int max = 0;
    	boolean [][] dp  = new boolean[s.length()+1][s.length()+1];

		for (int i = s.length()-1; i >=0 ; i--) {
			for (int j = i; j < s.length() ; j++) {
				if (s.charAt(i)==s.charAt(j)){
					if (j-i<2||dp[i+1][j-1]){
						dp[i][j] = true;

					}
					if (j-i+1>max && dp[i][j]){
						max = j-i+1;
						start = i;
						end = j;
					}
				}
			}
		}
		return s.substring(start,end+1);

	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
